package ligne2vie.topos.server.bo.geocell;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 #
 # Copyright 2010 Alexandre Gellibert
 #
 # Licensed under the Apache License, Version 2.0 (the "License");
 # you may not use this file except in compliance with the License.
 # You may obtain a copy of the License at
 #
 #     http://www.apache.org/licenses/LICENSE-2.0
 #
 # Unless required by applicable law or agreed to in writing, software
 # distributed under the License is distributed on an "AS IS" BASIS,
 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 # See the License for the specific language governing permissions and
 # limitations under the License.
 */

/**
 * Utils class to compute geocells.
 * 
 * @author api.roman.public@gmail.com (Roman Nurik)
 * @author (java portage) Alexandre Gellibert
 * 
 */
public final class GeocellUtils {

	// Geocell algorithm constants.
	public static final int GEOCELL_GRID_SIZE = 4;
	private static final String GEOCELL_ALPHABET = "0123456789abcdef";

	// Direction enumerations.
	private static final int[] NORTHWEST = new int[] { -1, 1 };
	private static final int[] NORTH = new int[] { 0, 1 };
	private static final int[] NORTHEAST = new int[] { 1, 1 };
	private static final int[] EAST = new int[] { 1, 0 };
	private static final int[] SOUTHEAST = new int[] { 1, -1 };
	private static final int[] SOUTH = new int[] { 0, -1 };
	private static final int[] SOUTHWEST = new int[] { -1, -1 };
	private static final int[] WEST = new int[] { -1, 0 };

	private static final int RADIUS = 6378135;

	private GeocellUtils() {
		// no instantiation allowed
	}

	/**
	 * Determines whether the given cells are collinear along a dimension.
	 * 
	 * Returns True if the given cells are in the same row (columnTest=False) or in the same column (columnTest=True).
	 * 
	 * @param cell1
	 *            : The first geocell string.
	 * @param cell2
	 *            : The second geocell string.
	 * @param columnTest
	 *            : A boolean, where False invokes a row collinearity test and 1 invokes a column collinearity test.
	 * @return A bool indicating whether or not the given cells are collinear in the given dimension.
	 */
	public static boolean collinear(String cell1, String cell2, boolean columnTest) {

		for (int i = 0; i < Math.min(cell1.length(), cell2.length()); i++) {
			int l1[] = subdivXY(cell1.charAt(i));
			int x1 = l1[0];
			int y1 = l1[1];
			int l2[] = subdivXY(cell2.charAt(i));
			int x2 = l2[0];
			int y2 = l2[1];

			// Check row collinearity (assure y's are always the same).
			if (!columnTest && y1 != y2) {
				return false;
			}

			// Check column collinearity (assure x's are always the same).
			if (columnTest && x1 != x2) {
				return false;
			}
		}
		return true;
	}

	/**
	 * 
	 * Calculates the grid of cells formed between the two given cells.
	 * 
	 * Generates the set of cells in the grid created by interpolating from the given Northeast geocell to the given
	 * Southwest geocell.
	 * 
	 * Assumes the Northeast geocell is actually Northeast of Southwest geocell.
	 * 
	 * 
	 * @param cellNE
	 *            : The Northeast geocell string.
	 * @param cellSW
	 *            : The Southwest geocell string.
	 * @return A list of geocell strings in the interpolation.
	 */
	public static List<String> interpolate(String cellNE, String cellSW) {
		// 2D array, will later be flattened.
		LinkedList<LinkedList<String>> cellSet = new LinkedList<LinkedList<String>>();
		LinkedList<String> cellFirst = new LinkedList<String>();
		cellFirst.add(cellSW);
		cellSet.add(cellFirst);

		// First get adjacent geocells across until Southeast--collinearity with
		// Northeast in vertical direction (0) means we're at Southeast.
		while (!collinear(cellFirst.getLast(), cellNE, true)) {
			String cellTmp = adjacent(cellFirst.getLast(), EAST);
			if (cellTmp == null) {
				break;
			}
			cellFirst.add(cellTmp);
		}

		// Then get adjacent geocells upwards.
		while (!cellSet.getLast().getLast().equalsIgnoreCase(cellNE)) {

			LinkedList<String> cellTmpRow = new LinkedList<String>();
			for (String g : cellSet.getLast()) {
				cellTmpRow.add(adjacent(g, NORTH));
			}
			if (cellTmpRow.getFirst() == null) {
				break;
			}
			cellSet.add(cellTmpRow);
		}

		// Flatten cellSet, since it's currently a 2D array.
		List<String> result = new ArrayList<String>();
		for (LinkedList<String> list : cellSet) {
			result.addAll(list);
		}
		return result;
	}

	/**
	 * Computes the number of cells in the grid formed between two given cells.
	 * 
	 * Computes the number of cells in the grid created by interpolating from the given Northeast geocell to the given
	 * Southwest geocell. Assumes the Northeast geocell is actually Northeast of Southwest geocell.
	 * 
	 * @param cellNE
	 *            : The Northeast geocell string.
	 * @param cellSW
	 *            : The Southwest geocell string.
	 * @return An int, indicating the number of geocells in the interpolation.
	 */
	public static int interpolationCount(String cellNE, String cellSW) {

		BoundingBox bboxNE = computeBox(cellNE);
		BoundingBox bboxSW = computeBox(cellSW);

		double cellLatSpan = bboxSW.getNorth() - bboxSW.getSouth();
		double cellLonSpan = bboxSW.getEast() - bboxSW.getWest();

		int numCols = (int) ((bboxNE.getEast() - bboxSW.getWest()) / cellLonSpan);
		int numRows = (int) ((bboxNE.getNorth() - bboxSW.getSouth()) / cellLatSpan);

		return numCols * numRows;
	}

	/**
	 * 
	 * Calculates all of the given geocell's adjacent geocells.
	 * 
	 * @param cell
	 *            : The geocell string for which to calculate adjacent/neighboring cells.
	 * @return A list of 8 geocell strings and/or None values indicating adjacent cells.
	 */

	public static List<String> allAdjacents(String cell) {
		List<String> result = new ArrayList<String>();
		for (int[] d : Arrays.asList(NORTHWEST, NORTH, NORTHEAST, EAST, SOUTHEAST, SOUTH, SOUTHWEST, WEST)) {
			result.add(adjacent(cell, d));
		}
		return result;
	}

	/**
	 * Calculates the geocell adjacent to the given cell in the given direction.
	 * 
	 * @param cell
	 *            : The geocell string whose neighbor is being calculated.
	 * @param dir
	 *            : An (x, y) tuple indicating direction, where x and y can be -1, 0, or 1. -1 corresponds to West for x
	 *            and South for y, and 1 corresponds to East for x and North for y. Available helper constants are
	 *            NORTH, EAST, SOUTH, WEST, NORTHEAST, NORTHWEST, SOUTHEAST, and SOUTHWEST.
	 * @return The geocell adjacent to the given cell in the given direction, or None if there is no such cell.
	 */
	public static String adjacent(String cell, int[] dir) {
		if (cell == null) {
			return null;
		}
		int dx = dir[0];
		int dy = dir[1];
		char[] cellAdjArr = cell.toCharArray(); // Split the geocell string characters into a list.
		int i = cellAdjArr.length - 1;

		while (i >= 0 && (dx != 0 || dy != 0)) {
			int l[] = subdivXY(cellAdjArr[i]);
			int x = l[0];
			int y = l[1];

			// Horizontal adjacency.
			if (dx == -1) { // Asking for left.
				if (x == 0) { // At left of parent cell.
					x = GEOCELL_GRID_SIZE - 1; // Becomes right edge of adjacent parent.
				} else {
					x--; // Adjacent, same parent.
					dx = 0; // Done with x.
				}
			} else if (dx == 1) { // Asking for right.
				if (x == GEOCELL_GRID_SIZE - 1) { // At right of parent cell.
					x = 0; // Becomes left edge of adjacent parent.
				} else {
					x++; // Adjacent, same parent.
					dx = 0; // Done with x.
				}
			}

			// Vertical adjacency.
			if (dy == 1) { // Asking for above.
				if (y == GEOCELL_GRID_SIZE - 1) { // At top of parent cell.
					y = 0; // Becomes bottom edge of adjacent parent.
				} else {
					y++; // Adjacent, same parent.
					dy = 0; // Done with y.
				}
			} else if (dy == -1) { // Asking for below.
				if (y == 0) { // At bottom of parent cell.
					y = GEOCELL_GRID_SIZE - 1; // Becomes top edge of adjacent parent.
				} else {
					y--; // Adjacent, same parent.
					dy = 0; // Done with y.
				}
			}

			int l2[] = { x, y };
			cellAdjArr[i] = subdivChar(l2);
			i--;
		}
		// If we're not done with y then it's trying to wrap vertically,
		// which is a failure.
		if (dy != 0) {
			return null;
		}

		// At this point, horizontal wrapping is done inherently.
		return new String(cellAdjArr);
	}

	/**
	 * Returns whether or not the given cell contains the given point.
	 * 
	 * @param cell
	 * @param point
	 * @return Returns whether or not the given cell contains the given point.
	 */
	public static boolean containsPoint(String cell, Point point) {
		return compute(point, cell.length()).equalsIgnoreCase(cell);
	}

	/**
	 * Returns the shortest distance between a point and a geocell bounding box.
	 * 
	 * If the point is inside the cell, the shortest distance is always to a 'edge' of the cell rectangle. If the point
	 * is outside the cell, the shortest distance will be to either a 'edge' or 'corner' of the cell rectangle.
	 * 
	 * @param cell
	 * @param point
	 * @return The shortest distance from the point to the geocell's rectangle, in meters.
	 */
	public static double pointDistance(String cell, Point point) {
		BoundingBox bbox = computeBox(cell);

		boolean betweenWE = bbox.getWest() <= point.getLon() && point.getLon() <= bbox.getEast();
		boolean betweenNS = bbox.getSouth() <= point.getLat() && point.getLat() <= bbox.getNorth();

		if (betweenWE) {
			if (betweenNS) {
				// Inside the geocell.
				return Math.min(
						Math.min(distance(point, new Point(bbox.getSouth(), point.getLon())),
								distance(point, new Point(bbox.getNorth(), point.getLon()))),
						Math.min(distance(point, new Point(point.getLat(), bbox.getEast())),
								distance(point, new Point(point.getLat(), bbox.getWest()))));
			} else {
				return Math.min(distance(point, new Point(bbox.getSouth(), point.getLon())),
						distance(point, new Point(bbox.getNorth(), point.getLon())));
			}
		} else {
			if (betweenNS) {
				return Math.min(distance(point, new Point(point.getLat(), bbox.getEast())),
						distance(point, new Point(point.getLat(), bbox.getWest())));
			} else {
				// TODO(romannurik): optimize
				return Math.min(
						Math.min(distance(point, new Point(bbox.getSouth(), bbox.getEast())),
								distance(point, new Point(bbox.getNorth(), bbox.getEast()))),
						Math.min(distance(point, new Point(bbox.getSouth(), bbox.getWest())),
								distance(point, new Point(bbox.getNorth(), bbox.getWest()))));
			}
		}
	}

	/**
	 * Computes the geocell containing the given point to the given resolution.
	 * 
	 * This is a simple 16-tree lookup to an arbitrary depth (resolution).
	 * 
	 * @param point
	 *            : The geotypes.Point to compute the cell for.
	 * @param resolution
	 *            : An int indicating the resolution of the cell to compute.
	 * @return The geocell string containing the given point, of length resolution.
	 */
	public static String compute(Point point, int resolution) {
		float north = 90.0f;
		float south = -90.0f;
		float east = 180.0f;
		float west = -180.0f;

		StringBuilder cell = new StringBuilder();
		while (cell.length() < resolution) {
			float subcellLonSpan = (east - west) / GEOCELL_GRID_SIZE;
			float subcellLatSpan = (north - south) / GEOCELL_GRID_SIZE;

			int x = Math
					.min((int) (GEOCELL_GRID_SIZE * (point.getLon() - west) / (east - west)), GEOCELL_GRID_SIZE - 1);
			int y = Math.min((int) (GEOCELL_GRID_SIZE * (point.getLat() - south) / (north - south)),
					GEOCELL_GRID_SIZE - 1);

			int l[] = { x, y };
			cell.append(subdivChar(l));

			south += subcellLatSpan * y;
			north = south + subcellLatSpan;

			west += subcellLonSpan * x;
			east = west + subcellLonSpan;
		}
		return cell.toString();
	}

	/**
	 * Computes the rectangular boundaries (bounding box) of the given geocell.
	 * 
	 * @param cell_
	 *            : The geocell string whose boundaries are to be computed.
	 * @return A geotypes.Box corresponding to the rectangular boundaries of the geocell.
	 */
	public static BoundingBox computeBox(String cell_) {
		if (cell_ == null) {
			return null;
		}

		BoundingBox bbox = new BoundingBox(90.0, 180.0, -90.0, -180.0);
		StringBuilder cell = new StringBuilder(cell_);
		while (cell.length() > 0) {
			double subcellLonSpan = (bbox.getEast() - bbox.getWest()) / GEOCELL_GRID_SIZE;
			double subcellLatSpan = (bbox.getNorth() - bbox.getSouth()) / GEOCELL_GRID_SIZE;

			int l[] = subdivXY(cell.charAt(0));
			int x = l[0];
			int y = l[1];

			bbox = new BoundingBox(bbox.getSouth() + subcellLatSpan * (y + 1), bbox.getWest() + subcellLonSpan
					* (x + 1), bbox.getSouth() + subcellLatSpan * y, bbox.getWest() + subcellLonSpan * x);

			cell.deleteCharAt(0);
		}

		return bbox;
	}

	/**
	 * Returns whether or not the given geocell string defines a valid geocell.
	 * 
	 * @param cell
	 * @return Returns whether or not the given geocell string defines a valid geocell.
	 */
	public static boolean isValid(String cell) {
		if (cell == null || cell.trim().length() == 0) {
			return false;
		}
		for (char c : cell.toCharArray()) {
			if (GEOCELL_ALPHABET.indexOf(c) < 0) {
				return false;
			}
		}
		return true;
	}

	/**
	 * Returns the (x, y) of the geocell character in the 4x4 alphabet grid.
	 * 
	 * @param char_
	 * @return Returns the (x, y) of the geocell character in the 4x4 alphabet grid.
	 */
	public static int[] subdivXY(char char_) {
		// NOTE: This only works for grid size 4.
		int charI = GEOCELL_ALPHABET.indexOf(char_);
		return new int[] { (charI & 4) >> 1 | (charI & 1) >> 0, (charI & 8) >> 2 | (charI & 2) >> 1 };
	}

	/**
	 * Returns the geocell character in the 4x4 alphabet grid at pos. (x, y).
	 * 
	 * @param pos
	 * @return Returns the geocell character in the 4x4 alphabet grid at pos. (x, y).
	 */
	public static char subdivChar(int[] pos) {
		// NOTE: This only works for grid size 4.
		return GEOCELL_ALPHABET.charAt((pos[1] & 2) << 2 | (pos[0] & 2) << 1 | (pos[1] & 1) << 1 | (pos[0] & 1) << 0);
	}

	/**
	 * Calculates the great circle distance between two points (law of cosines).
	 * 
	 * @param p1
	 *            : indicating the first point.
	 * @param p2
	 *            : indicating the second point.
	 * @return The 2D great-circle distance between the two given points, in meters.
	 */
	public static double distance(Point p1, Point p2) {
		double p1lat = Math.toRadians(p1.getLat());
		double p1lon = Math.toRadians(p1.getLon());
		double p2lat = Math.toRadians(p2.getLat());
		double p2lon = Math.toRadians(p2.getLon());
		return RADIUS
				* Math.acos(makeDoubleInRange(Math.sin(p1lat) * Math.sin(p2lat) + Math.cos(p1lat) * Math.cos(p2lat)
						* Math.cos(p2lon - p1lon)));
	}

	/**
	 * This function is used to fix issue 10: GeocellUtils.distance(...) uses Math.acos(arg) method. In some cases arg >
	 * 1 (i.e 1.0000000002), so acos cannot be calculated and the method returns NaN.
	 * 
	 * @param d
	 * @return a double between -1 and 1
	 */
	public static double makeDoubleInRange(double d) {
		double result = d;
		if (d > 1) {
			result = 1;
		} else if (d < -1) {
			result = -1;
		}
		return result;
	}

	/**
	 * Returns the edges of the rectangular region containing all of the given geocells, sorted by distance from the
	 * given point, along with the actual distances from the point to these edges.
	 * 
	 * @param cells
	 *            : The cells (should be adjacent) defining the rectangular region whose edge distances are requested.
	 * @param point
	 *            : The point that should determine the edge sort order.
	 * @return A list of (direction, distance) tuples, where direction is the edge and distance is the distance from the
	 *         point to that edge. A direction value of (0,-1), for example, corresponds to the South edge of the
	 *         rectangular region containing all of the given geocells.
	 * 
	 *         TODO(romannurik): Assert that lat,lon are actually inside the geocell.
	 */
	public static List<Tuple<int[], Double>> distanceSortedEdges(List<String> cells, Point point) {
		List<BoundingBox> boxes = new ArrayList<BoundingBox>();
		for (String cell : cells) {
			boxes.add(computeBox(cell));
		}
		double maxNorth = Double.NEGATIVE_INFINITY;
		double maxEast = Double.NEGATIVE_INFINITY;
		double maxSouth = Double.POSITIVE_INFINITY;
		double maxWest = Double.POSITIVE_INFINITY;
		for (BoundingBox box : boxes) {
			maxNorth = Math.max(maxNorth, box.getNorth());
			maxEast = Math.max(maxEast, box.getEast());
			maxSouth = Math.min(maxSouth, box.getSouth());
			maxWest = Math.min(maxWest, box.getWest());
		}
		List<Tuple<int[], Double>> result = new ArrayList<Tuple<int[], Double>>();
		result.add(new Tuple<int[], Double>(SOUTH, distance(new Point(maxSouth, point.getLon()), point)));
		result.add(new Tuple<int[], Double>(NORTH, distance(new Point(maxNorth, point.getLon()), point)));
		result.add(new Tuple<int[], Double>(WEST, distance(new Point(point.getLat(), maxWest), point)));
		result.add(new Tuple<int[], Double>(EAST, distance(new Point(point.getLat(), maxEast), point)));
		Collections.sort(result, new DoubleTupleComparator());
		return result;
	}

}
